<!DOCTYPE html>
<html lang="zh-cn">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>第一类问题的证明</title>

</head>
<body>
1、对齐
为了证明方便，我们将循环队列的末尾对齐。
由于队列至少前进1位，我们选定末尾都[0,2]的状态。
<!-- 没心情写，很郁闷。想不出结果。觉得人生完蛋了 -->
想法是，以状态机所示的步骤，如果末尾位需要出现循环，那么需要队列前面的位进行协调同步。
但是以原有队列长度是无法满足同步，同步需要在队列前方引入更多的位数，导致该队列的位变得无限长。
<!-- 逆推导的可能性太多，一下子没法组织起来。 -->
新增末位都是[0,2],要留意该位的变化过程

<hr>

上面的想法没有一点进展。
认真了解了一下图灵机，觉得应该尝试用等价的图灵机证明：
1、首先将问题转换为图灵机，纸带(track)状态包括队首、队尾，指令包括让指针(robot)返回队首，重复3n+1计算方法的指令
2、尝试证明，如果不需要返回队首，而是处理队尾部分后，再回头处理队首的图灵机，纸带的长度是有限
3、尝试证明两类图灵机是等价的。
</body>
</html>